SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Lehmer code</title>

</head>

Lehmer code

</h1>

</header>

In <a href="Mathematics" title="Mathematics">mathematics</a> and in particular in <a href="Combinatorics" title="Combinatorics">combinatorics</a>, the Lehmer code is a particular way to <a href="Encoding" class="mw-redirect" title="Encoding">encode</a> each possible <a href="Permutation" title="Permutation">permutation</a> of a sequence of n numbers. It is an instance of a scheme for <a href="Permutation#Numbering_permutations" title="Permutation">numbering permutations</a> and is an example of an <a href="Inversion_(discrete_mathematics)" title="Inversion (discrete mathematics)">inversion</a> table.

The Lehmer code is named in reference to <a href="D._H._Lehmer" title="D. H. Lehmer">D. H. Lehmer</a>,<a href="#cite_note-lehmer-1">[1]</a> but the code had been known since 1888 at least.<a href="#cite_note-laisant-2">[2]</a>

The Lehmer code makes use of the fact that there are

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n!=n\times (n-1)\times \cdots \times 2\times 1}</annotation>

</semantics>

</math><img src="./0f6f869ce2d8e2880651f1c8778f1aaab9e10e79.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.151ex; height:2.843ex;" alt="{\displaystyle n!=n\times (n-1)\times \cdots \times 2\times 1}" loading="lazy"></dd></dl>

permutations of a sequence of n numbers. If a permutation σ is specified by the sequence (σ1, ..., σn) of its images of 1, ..., n, then it is encoded by a sequence of n numbers, but not all such sequences are valid since every number must be used only once. By contrast the encodings considered here choose the first number from a set of n values, the next number from a fixed set of n − 1 values, and so forth decreasing the number of possibilities until the last number for which only a single fixed value is allowed; every sequence of numbers chosen from these sets encodes a single permutation. While several <a href="Encoding" class="mw-redirect" title="Encoding">encodings</a> can be defined, the Lehmer code has several additional useful properties; it is the sequence

<dl><dd><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{where}}\quad L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\},}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mtext>where</mtext>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{where}}\quad L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\},}</annotation>

</semantics>

</math><img src="./30ea837af6169090dcaa7e428a852d7c8541e377.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:64.903ex; height:3.009ex;" alt="{\displaystyle L(\sigma )=(L(\sigma )_{1},\ldots ,L(\sigma )_{n})\quad {\text{where}}\quad L(\sigma )_{i}=\#\{j>i:\sigma _{j}<\sigma _{i}\},}" loading="lazy"></dd></dl>

in other words the term L(σ)i counts the number of terms in (σ1, ..., σn) to the right of σi that are smaller than it, a number between 0 and n − i, allowing for n + 1 − i different values.

A pair of indices (i,j) with i < j and σi > σj is called an inversion of σ, and L(σ)i counts the number of inversions (i,j) with i fixed and varying j. It follows that L(σ)1 + L(σ)2 + … + L(σ)n is the total number of inversions of σ, which is also the number of adjacent transpositions that are needed to transform the permutation into the identity permutation. Other properties of the Lehmer code include that the <a href="Lexicographical_order" class="mw-redirect" title="Lexicographical order">lexicographical order</a> of the encodings of two permutations is the same as that of their sequences (σ1, ..., σn), that any value 0 in the code represents a right-to-left minimum in the permutation (i.e., a σi smaller than any σj to its right), and a value n − i

at position i similarly signifies a right-to-left maximum, and that the Lehmer code of σ coincides with the <a href="Factorial_number_system" title="Factorial number system">factorial number system</a> representation of its position in the list of permutations of n in lexicographical order (numbering the positions starting from 0).

Variations of this encoding can be obtained by counting inversions (i,j) for fixed j rather than fixed i, by counting inversions with a fixed smaller value σj rather than smaller index i, or by counting non-inversions rather than inversions; while this does not produce a fundamentally different type of encoding, some properties of the encoding will change correspondingly. In particular counting inversions with a fixed smaller value σj gives the inversion table of σ, which can be seen to be the Lehmer code of the inverse permutation.

<div class="mw-heading mw-heading2"><h2 id="Encoding_and_decoding">Encoding and decoding</h2></div>

The usual way to prove that there are n! different permutations of n objects is to observe that the first object can be chosen in n different ways, the next object in n − 1 different ways (because choosing the same number as the first is forbidden), the next in n − 2 different ways (because there are now 2 forbidden values), and so forth. Translating this freedom of choice at each step into a number, one obtains an encoding algorithm, one that finds the Lehmer code of a given permutation. One need not suppose the objects permuted to be numbers, but one needs a <a href="Total_ordering" class="mw-redirect" title="Total ordering">total ordering</a> of the set of objects. Since the code numbers are to start from 0, the appropriate number to encode each object σi by is the number of objects that were available at that point (so they do not occur before position i), but which are smaller than the object σi actually chosen. (Inevitably such objects must appear at some position j > i, and (i,j) will be an inversion, which shows that this number is indeed L(σ)i.)

This number to encode each object can be found by direct counting, in several ways (directly counting inversions, or correcting the total number of objects smaller than a given one, which is its sequence number starting from 0 in the set, by those that are unavailable at its position). Another method which is in-place, but not really more efficient, is to start with the permutation of {0, 1, ... n − 1} obtained by representing each object by its mentioned sequence number, and then for each entry x, in order from left to right, correct the items to its right by subtracting 1 from all entries (still) greater than x (to reflect the fact that the object corresponding to x is no longer available). Concretely a Lehmer code for the permutation B,F,A,G,D,E,C of letters, ordered alphabetically, would first give the list of sequence numbers 1,5,0,6,3,4,2, which is successively transformed

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}\mathbf {1} &5&0&6&3&4&2\\1&\mathbf {4} &0&5&2&3&1\\1&4&\mathbf {0} &4&2&3&1\\1&4&0&\mathbf {3} &1&2&0\\1&4&0&3&\mathbf {1} &2&0\\1&4&0&3&1&\mathbf {1} &0\\1&4&0&3&1&1&\mathbf {0} \\\end{matrix}}}</annotation>

</semantics>

</math><img src="./22a33e7dfbddbb2034edb8748c20bb7a7ffbbf77.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -10.671ex; width:24.044ex; height:22.343ex;" alt="{\displaystyle {\begin{matrix}\mathbf {1} &5&0&6&3&4&2\\1&\mathbf {4} &0&5&2&3&1\\1&4&\mathbf {0} &4&2&3&1\\1&4&0&\mathbf {3} &1&2&0\\1&4&0&3&\mathbf {1} &2&0\\1&4&0&3&1&\mathbf {1} &0\\1&4&0&3&1&1&\mathbf {0} \\\end{matrix}}}" loading="lazy"></dd></dl>

where the final line is the Lehmer code (at each line one subtracts 1 from the larger entries to the right of the boldface element to form the next line).

For decoding a Lehmer code into a permutation of a given set, the latter procedure may be reversed: for each entry x, in order from right to left, correct the items to its right by adding 1 to all those (currently) greater than or equal to x; finally interpret the resulting permutation of {0, 1, ... n − 1} as sequence numbers (which amounts to adding 1 to each entry if a permutation of {1, 2, ... n} is sought). Alternatively the entries of the Lehmer code can be processed from left to right, and interpreted as a number determining the next choice of an element as indicated above; this requires maintaining a list of available elements, from which each chosen element is removed. In the example this would mean choosing element 1 from {A,B,C,D,E,F,G} (which is B) then element 4 from {A,C,D,E,F,G} (which is F), then element 0 from {A,C,D,E,G} (giving A) and so on, reconstructing the sequence B,F,A,G,D,E,C.

<div class="mw-heading mw-heading2"><h2 id="Applications_to_combinatorics_and_probabilities">Applications to combinatorics and probabilities</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Independence_of_relative_ranks">Independence of relative ranks</h3></div>

The Lehmer code defines a bijection from the <a href="Symmetric_group" title="Symmetric group">symmetric group</a> Sn to the Cartesian product <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [n]\times [n-1]\times \cdots \times [2]\times [1]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [n]\times [n-1]\times \cdots \times [2]\times [1]}</annotation>

</semantics>

</math><img src="./e9083866075373cd9c8bebc725636b5d3fa667e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.377ex; height:2.843ex;" alt="{\displaystyle [n]\times [n-1]\times \cdots \times [2]\times [1]}" loading="lazy">, where [k] designates the k-element set <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1,\ldots ,k-1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{0,1,\ldots ,k-1\}}</annotation>

</semantics>

</math><img src="./f3269d4d896f77d7be6e47d0cc35f54acdd15f98.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.076ex; height:2.843ex;" alt="{\displaystyle \{0,1,\ldots ,k-1\}}" loading="lazy">. As a consequence, under the <a href="Uniform_distribution_(discrete)" class="mw-redirect" title="Uniform distribution (discrete)">uniform distribution</a> on Sn, the component L(σ)i defines a uniformly distributed <a href="Random_variable" title="Random variable">random variable</a> on [n − i], and these random variables are mutually <a href="Independence_(probability_theory)" title="Independence (probability theory)">independent</a>, because they are projections on different factors of a <a href="Cartesian_product" title="Cartesian product">Cartesian product</a>.

<div class="mw-heading mw-heading3"><h3 id="Number_of_right-to-left_minima_and_maxima">Number of right-to-left minima and maxima</h3></div>

Definition : In a sequence u=(uk)1≤k≤n, there is right-to-left minimum (resp. maximum) at rank k if uk is strictly smaller (resp. strictly bigger) than each element ui with i>k, i.e., to its right.

Let B(k) (resp. H(k)) be the event "there is right-to-left minimum (resp. maximum) at rank k", i.e. B(k) is the set of the permutations <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle \ {\mathfrak {S}}_{n}}">

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle \ {\mathfrak {S}}_{n}}</annotation>

</semantics>

</math><img src="./f52258ea58e3cb34d89e5a0206a267d0a13ce4c8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.908ex; height:1.843ex;" alt="{\displaystyle \scriptstyle \ {\mathfrak {S}}_{n}}" loading="lazy"> which exhibit a right-to-left minimum (resp. maximum) at rank k. We clearly have

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{\omega \in B(k)\}\Leftrightarrow \{L(k,\omega )=0\}\quad {\text{and}}\quad \{\omega \in H(k)\}\Leftrightarrow \{L(k,\omega )=k-1\}.}</annotation>

</semantics>

</math><img src="./6f2a0f206aaaa2c5ddb2dee402496b498d73cb58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:70.749ex; height:2.843ex;" alt="{\displaystyle \{\omega \in B(k)\}\Leftrightarrow \{L(k,\omega )=0\}\quad {\text{and}}\quad \{\omega \in H(k)\}\Leftrightarrow \{L(k,\omega )=k-1\}.}" loading="lazy"></div>

Thus the number Nb(ω) (resp. Nh(ω)) of right-to-left minimum (resp. maximum) for the permutation ω can be written as a sum of independent <a href="Bernoulli_random_variable" class="mw-redirect" title="Bernoulli random variable">Bernoulli random variables</a> each with a respective parameter of 1/k :

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{B(k)}\quad {\text{and}}\quad N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{H(k)}.}</annotation>

</semantics>

</math><img src="./c6cf58e2ce486fed1f700436af5ae029292cc456.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:50.277ex; height:5.843ex;" alt="{\displaystyle N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{B(k)}\quad {\text{and}}\quad N_{b}(\omega )=\sum _{1\leq k\leq n}\ 1\!\!1_{H(k)}.}" loading="lazy"></div>

Indeed, as L(k) follows the uniform law on <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \scriptstyle \ [\![1,k]\!],}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \scriptstyle \ [\![1,k]\!],}</annotation>

</semantics>

</math><img src="./634ca8608aae56d85a27e44a6215624d61bb3e2e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.229ex; height:2.176ex;" alt="{\displaystyle \scriptstyle \ [\![1,k]\!],}" loading="lazy">

</mrow>

</mrow>

</mrow>

</mrow>

<mfrac>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {P} (B(k))=\mathbb {P} (L(k)=0)=\mathbb {P} (H(k))=\mathbb {P} (L(k)=k-1)={\tfrac {1}{k}}.}</annotation>

</semantics>

</math><img src="./2708d4893d1d4bb9c2334ece0324f4452e8b458a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:59.3ex; height:3.676ex;" alt="{\displaystyle \mathbb {P} (B(k))=\mathbb {P} (L(k)=0)=\mathbb {P} (H(k))=\mathbb {P} (L(k)=k-1)={\tfrac {1}{k}}.}" loading="lazy"></div>

The <a href="Generating_function" title="Generating function">generating function</a> for the Bernoulli random variable <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\!\!1_{B(k)}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\!\!1_{B(k)}}</annotation>

</semantics>

</math><img src="./bca752cb4e501b29b95e230cd652274c7ec4cd6f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:5.166ex; height:3.009ex;" alt="{\displaystyle 1\!\!1_{B(k)}}" loading="lazy"> is

<msub>

</mrow>

</msub>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{k}(s)={\frac {k-1+s}{k}},}</annotation>

</semantics>

</math><img src="./98f39ae02534b5fbfdcbf4cdf6e3f8f1b29a1de9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.005ex; width:19.542ex; height:5.509ex;" alt="{\displaystyle G_{k}(s)={\frac {k-1+s}{k}},}" loading="lazy"></div>

therefore the generating function of Nb is

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

<mfrac>

<msup>

<mover>

</mover>

</mrow>

</msup>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(s)=\prod _{k=1}^{n}G_{k}(s)\ =\ {\frac {s^{\overline {n}}}{n!}}}</annotation>

</semantics>

</math><img src="./c6111ad1a5c0934127160c0b67fe82ba0d8dcab1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:24.495ex; height:7.009ex;" alt="{\displaystyle G(s)=\prod _{k=1}^{n}G_{k}(s)\ =\ {\frac {s^{\overline {n}}}{n!}}}" loading="lazy"></div>

(using the <a href="Falling_and_rising_factorials" title="Falling and rising factorials">rising factorial</a> notation),

which allows us to recover the product formula for the generating function of the

<a href="Stirling_numbers_of_the_first_kind" title="Stirling numbers of the first kind">Stirling numbers of the first kind</a> (unsigned).

<div class="mw-heading mw-heading3"><h3 id="The_secretary_problem">The secretary problem</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Secretary_problem" title="Secretary problem">Secretary problem</a></div>

This is an optimal stop problem, a classic in decision theory, statistics and applied probabilities, where a random permutation is gradually revealed through the first elements of its Lehmer code, and where the goal is to stop exactly at the element k such as σ(k)=n, whereas the only available information (the k first values of the Lehmer code) is not sufficient to compute σ(k).

In less mathematical words: a series of n applicants are interviewed one after the other. The interviewer must hire the best applicant, but must make his decision (“Hire” or “Not hire”) on the spot, without interviewing the next applicant (and a fortiori without interviewing all applicants).

The interviewer thus knows the rank of the kth applicant, therefore, at the moment of making his kth decision, the interviewer knows only the k first elements of the Lehmer code whereas he would need to know all of them to make a well informed decision.

To determine the optimal strategies (i.e. the strategy maximizing the probability of a win), the statistical properties of the Lehmer code are crucial.

Allegedly, <a href="Johannes_Kepler" title="Johannes Kepler">Johannes Kepler</a> clearly exposed this <a href="Secretary_problem" title="Secretary problem">secretary problem</a> to a friend of his at a time when he was trying to make up his mind and choose one out eleven prospective brides as his second wife. His first marriage had been an unhappy one, having been arranged without himself being consulted, and he was thus very concerned that he could reach the right decision.<a href="#cite_note-ferguson-3">[3]</a>

<div class="mw-heading mw-heading2"><h2 id="Similar_concepts">Similar concepts</h2></div>

Several related constructions have also been put into use. One of them is often called inversion vector, e.g. by <a href="Wolfram_Alpha" class="mw-redirect" title="Wolfram Alpha">Wolfram Alpha</a>.

See also <a href="Inversion_(discrete_mathematics)#Inversion_related_vectors" title="Inversion (discrete mathematics)">Inversion (discrete mathematics) § Inversion related vectors</a>.

/* start https://en.wikipedia.org/ */

.mw-parser-output .portalbox{padding:0;margin:0.5em 0;display:table;box-sizing:border-box;max-width:175px;list-style:none}.mw-parser-output .portalborder{border:1px solid var(--border-color-base,#a2a9b1);padding:0.1em;background:var(--background-color-neutral-subtle,#f8f9fa)}.mw-parser-output .portalbox-entry{display:table-row;font-size:85%;line-height:110%;height:1.9em;font-style:italic;font-weight:bold}.mw-parser-output .portalbox-image{display:table-cell;padding:0.2em;vertical-align:middle;text-align:center}.mw-parser-output .portalbox-link{display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle}@media(min-width:720px){.mw-parser-output .portalleft{margin:0.5em 1em 0.5em 0}.mw-parser-output .portalright{clear:right;float:right;margin:0.5em 0 0.5em 1em}}

/* end https://en.wikipedia.org/ */

</style>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFLehmer1960" class="citation cs2"><a href="D._H._Lehmer" title="D. H. Lehmer">Lehmer, D.H.</a> (1960), "Teaching combinatorial tricks to a computer", Combinatorial Analysis, Proceedings of Symposia in Applied Mathematics, vol. 10, pp. 179–193, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1090%2Fpsapm%2F010%2F0113289">10.1090/psapm/010/0113289</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-8218-1310-2</bdi>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0113289">0113289</a></cite> <code class="cs1-code">{{citation}}</code>: ISBN / Date incompatibility (help)

</li>

<cite id="CITEREFLaisant1888" class="citation cs2 cs1-prop-foreign-lang-source"><a href="Charles-Ange_Laisant" title="Charles-Ange Laisant">Laisant, Charles-Ange</a> (1888), <a rel="nofollow" class="external text" href="http://www.numdam.org/item?id=BSMF_1888__16__176_0">"Sur la numération factorielle, application aux permutations"</a> [On factorial numbering, application to permutations], Bulletin de la Société Mathématique de France (in French), 16: 176–183, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.24033%2Fbsmf.378">10.24033/bsmf.378</a></cite>

</li>

<li id="cite_note-ferguson-3"><a href="#cite_ref-ferguson_3-0">^</a> <cite id="CITEREFFerguson1989" class="citation cs2"><a href="Thomas_S._Ferguson" title="Thomas S. Ferguson">Ferguson, Thomas S.</a> (August 1989), <a rel="nofollow" class="external text" href="https://www2.math.upenn.edu/~ted/210F10/References/Secretary.pdf">"Who solved the secretary problem?"</a> (PDF), Statistical Science, 4 (3): 282–289, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1214%2Fss%2F1177012493">10.1214/ss/1177012493</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/2245639">2245639</a></cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Bibliography">Bibliography</h2></div>

<ul><li><cite id="CITEREFMantaciRakotondrajao2001" class="citation cs2">Mantaci, Roberto; Rakotondrajao, Fanja (2001), <a rel="nofollow" class="external text" href="https://web.archive.org/web/20041116061630/http://www.dmtcs.org/volumes/abstracts/pspapers/dm040203.ps">"A permutation representation that knows what "Eulerian" means"</a>, Discrete Mathematics and Theoretical Computer Science (4): 101–108, archived from <a rel="nofollow" class="external text" href="http://www.dmtcs.org/volumes/abstracts/pspapers/dm040203.ps">the original</a> on 2004-11-16</cite></li>

<li><cite id="CITEREFKnuth1981" class="citation cs2"><a href="Donald_Knuth" title="Donald Knuth">Knuth, Donald</a> (1981), The Art of Computer Programming, vol. 3, Reading: Addison-Wesley, pp. 12–13</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-08-08" href="https://en.wikipedia.org/wiki/?title=Lehmer_code&oldid=1304783060">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>